/*
 * @Author: gitee_com_zb
 * @Date: 2024-11-15 13:14:45
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-11-15 13:14:48
 * @FilePath: /lzb/GiteeCode/algorithm/优选算法44.快速排序(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/sort-an-array
 */
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        /***** version 1.不讲武德 *****/
        // sort(nums.begin(),nums.end());
        // return nums;

        /***** version 2.快速排序 *****/
        srand(time(nullptr));
        qsort(nums, 0, nums.size()-1);
        return nums;
    }
    // 快排
    void qsort(vector<int>& nums, int l, int r) {
        if(l >= r) return;
        int key = getRandom(nums, l, r); // 获取随机基准值
        int i = l, left = l - 1, right = r + 1;
        while(i < right) {
            if(nums[i] < key) swap(nums[++left],nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right],nums[i]);
        }
        // 按照基准值将数组分为了三个区间 [l,left] [left+1,right-1] [right,r]
        qsort(nums, l, left);
        qsort(nums, right, r);
    }
    // 获取随机基准值
    int getRandom(vector<int>& nums, int left, int right) {
        int r = rand();
        return nums[left + r % (right - left + 1)];
    }
};